import java.util.*;
//串联所有单词的子串
public class leetcode30 {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> list=new ArrayList<>();
        Map<String,Integer> map1=new HashMap<>();
        for(String x:words){
            map1.put(x,map1.getOrDefault(x,0)+1);
        }
        int len=words[0].length();//每一个单词的长度
        int m=words.length;//单词个数
        for(int i=0;i<len;i++){
            Map<String,Integer> map2=new HashMap<>();
            int count=0;
            int left=i;
            for(int right=i;right+len<=s.length();right+=len){
                //进窗口
                String in=s.substring(right,right+len);
                map2.put(in,map2.getOrDefault(in,0)+1);
                if(map2.get(in)<=map1.getOrDefault(in,0)){
                    count++;
                }
                if(right-left+1>len*m){
                    String out=s.substring(left,left+len);
                    if(map2.get(out)<=map1.getOrDefault(out,0)){
                        count--;
                    }
                    map2.put(out,map2.get(out)-1);
                    left+=len;
                }
                if(count==m){
                    list.add(left);
                }
            }
        }
        return list;
    }
}
